/**
 * 不同的二叉树
 *
 * 给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值
 * 从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
 *
 * 示例 1：
 * 输入：n = 3
 * 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：[[1]]
 *
 * 提示：
 * 1 <= n <= 8
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 递归, 我们处理好递归要干什么就可以了
 * 我们的递归是要将一个区间的所有搜索树全都排列出来的
 * 也就是我们需要给两个参数, 并且返回值要是一个集合
 * 用来存储二叉搜索树的集合
 * 时间复杂度 : O(4 ^ n / n ^ (1/2))
 * 空间复杂度 : O(4 ^ n / n ^ (1/2))
 */

public class Main {
    public List<TreeNode> generateTrees(int n) {
        return dfs(1, n);
    }

    public List<TreeNode> dfs(int start, int end) {

        // 这个是储存可能的集合
        List<TreeNode> ans = new ArrayList<>();

        // 要是下标不合条件, 直接这个集合存储空
        if (start > end) {
            ans.add(null);
            return ans;
        }

        // 要是区间只有一个数
        // 只有一种可能性, 加入集合
        if (start == end) {
            ans.add(new TreeNode(start));
            return ans;
        }

        // 这里我们遍历所有的节点, 用来作头结点
        for (int i = start; i <= end; i++) {

            // 因为是搜索二叉树所以要注意左右节点与根节点的大小
            // 左子树
            List<TreeNode> leftTrees = dfs(start, i - 1);

            // 右字数
            List<TreeNode> rightTrees = dfs(i + 1, end);

            // 这里组合所有的左子树与右子树
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    ans.add(root);
                }
            }
        }

        // 返回结果
        return ans;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}